#include <stdio.h>
#include <stdlib.h>

typedef struct AVLNode *PtrToAVLNode;
struct AVLNode{
    int Key;
    PtrToAVLNode Left;
    PtrToAVLNode Right;
    int Height;
};
typedef PtrToAVLNode AVLTree;

AVLTree Insert ( AVLTree T, int Key );
void PostOrderPrint( AVLTree T ); /* details omitted */
void InOrderPrint( AVLTree T );   /* details omitted */

int main()
{
    int N, Key, i;
    AVLTree T = NULL;
    
    scanf("%d", &N);
    for ( i=0; i<N; i++ ) {
        scanf("%d", &Key);
        T = Insert( T, Key );
    }
    PostOrderPrint( T );
    InOrderPrint( T );
    
    return 0;
}
/* Your function will be put here */
int max(int a,int b)
{
    return a>b?a:b;
}
int getHeight(AVLTree T)
{
    return T?T->Height:0;
}
AVLTree RotateR(AVLTree p)
{
    AVLTree tmp=p->Left;
    p->Left=tmp->Right;
    tmp->Right=p;
    p->Height=max(getHeight(p->Left),getHeight(p->Right))+1;
    tmp->Height=max(getHeight(tmp->Left),getHeight(tmp->Right))+1;
    return tmp;
}
AVLTree RotateL(AVLTree p)
{
    AVLTree tmp=p->Right;
    p->Right=tmp->Left;
    tmp->Left=p;
    p->Height=max(getHeight(p->Left),getHeight(p->Right))+1;
    tmp->Height=max(getHeight(tmp->Left),getHeight(tmp->Right))+1;
    return tmp;
}
AVLTree RotateLR(AVLTree A)
{
    A->Left=RotateL(A->Left);
    return RotateR(A);
}
AVLTree RotateRL(AVLTree A)
{
    A->Right=RotateR(A->Right);
    return RotateL(A);
}

AVLTree Insert ( AVLTree T, int Key )
{
    if(!T)
    {
        T=(AVLTree)malloc(sizeof (struct AVLNode));
        T->Key=Key;
        T->Left=T->Right=NULL;
        T->Height=1;
    }
    else if(Key<T->Key)
    {
        T->Left=Insert(T->Left,Key);
        if(getHeight(T->Left)-getHeight(T->Right)>1)
            if(T->Left->Key>Key)
                T=RotateR(T);
            else
                T=RotateLR(T);
    }
    else if(T->Key<Key)
    {
        T->Right=Insert(T->Right,Key);
        if(getHeight(T->Right)-getHeight(T->Left)>1)
            if(T->Right->Key<Key)
                T=RotateL(T);
            else
                T=RotateRL(T);
    }
    T->Height=max(getHeight(T->Left),getHeight(T->Right))+1;
    return T;
}